// Package _7_BuildTree
// Date        : 2022/12/6 11:56
// Version     : 1.0.0
// Author      : 代码小学生王木木
// Email       : 18574945291@163.com
// Description : https://leetcode.cn/problems/zhong-jian-er-cha-shu-lcof/?favorite=xb9nqhhg
package _7_BuildTree

//Definition for a binary tree node.
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// 给定二叉树的前序遍历和中序遍历的结构，推导二叉树
func buildTree(preorder []int, inorder []int) *TreeNode {
	if len(preorder) == 0 || len(preorder) != len(inorder) {
		return nil
	}
	rootVal := preorder[0]
	findIndex := -1
	root := &TreeNode{
		Val: rootVal,
	}
	// 寻找左子树
	for i, v := range inorder {
		if v == rootVal {
			findIndex = i
			break
		}
	}
	// 切分数组
	midLeft := inorder[:findIndex]
	midRight := inorder[findIndex+1:] // +1 的目的是剔除中序遍历的根节点
	preorder = preorder[1:]           // 前序遍历也要砍掉根节点
	preLeft := preorder[:len(midLeft)]
	preRight := preorder[len(midLeft):]
	root.Left = buildTree(preLeft, midLeft)
	root.Right = buildTree(preRight, midRight)

	return root
}
